package tree;

/**
 * @Author wangtengyu
 * @Create 2018-09-14-16:17 二叉搜索树，不创建新的节点，只改变指针，生成一个排序的双向链表
 */
public class ConvertToLink {

  public IntTreeNode convert(IntTreeNode root) {
    if (root == null) {
      return null;
    }

    //到最后，这个节点位于双向链表的尾部
    IntTreeNode tail = null;

    tail = convert(root, tail);
    IntTreeNode tailForIterator = tail;
    while (tailForIterator != null) {
      System.out.print(tailForIterator.getValue() + " ");
      tailForIterator = tailForIterator.getLeft();
    }
    System.out.println();
    //双向链表头节点
    IntTreeNode head = tail;
    while (head.getLeft() != null) {
      head = head.getLeft();
    }
    return head;
  }

  private IntTreeNode convert(IntTreeNode current, IntTreeNode tail) {
    if (current == null) {
      return null;
    }
    if (current.getLeft() != null) {
      tail = convert(current.getLeft(), tail);
    }

    //根据出口情况进行判断
    current.setLeft(tail);
    if (tail != null) {
      tail.setRight(current);
    }
    tail = current;
//        System.out.println(tail.getValue());

    if (current.getRight() != null) {
      tail = convert(current.getRight(), tail);
    }
    return tail;
  }


  public static void main(String[] args) {
    IntTreeNode root = new IntTreeNode(10);
    root.setLeft(new IntTreeNode(6));
    root.getLeft().setLeft(new IntTreeNode(4));
    root.getLeft().setRight(new IntTreeNode(8));
    root.getLeft().getRight().setLeft(new IntTreeNode(7));
    root.getLeft().getRight().setRight(new IntTreeNode(9));
    root.setRight(new IntTreeNode(14));
    root.getRight().setLeft(new IntTreeNode(12));
    root.getRight().setRight(new IntTreeNode(16));

    ConvertToLink convertToLink = new ConvertToLink();
    IntTreeNode head = convertToLink.convert(root);
    while (head != null) {
      System.out.print(head.getValue() + " ");
      head = head.getRight();
    }


  }


}
